package ext;

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import org.junit.Test;

import util.ArrayGenerator;
import util.BracketUtils;

public class Zong {

    // 16. 算法题 : 最长递增子序列 ，如有多个，按照字典序输出第一个。
    public List<Integer> maxLength(int[] nums) {
        int n = nums.length, res = 1;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = 1;
        for (int i = 1; i < n; i++) {
            int max = 0;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && f[j] > max) {
                    g[i] = j;
                    f[i] = f[j] + 1;
                    max = f[j];
                }
            }
            res = Math.max(f[i], res);
        }
        Deque<Integer> deque = new ArrayDeque<>();
        int last = 0;
        while (f[last] < res) {
            last++;
        }
        while (f[last] > 0) {
            int t = last;
            deque.offerFirst(nums[last]);
            last = g[last];
            if (last == t) {
                break;
            }
        }
        return new ArrayList<>(deque);
    }

    @Test
    public void test() {
        int[] nums = new int[] { 1, 2, 8, 4, 4 };
        System.out.println(maxLength(nums));
    }

    public List<String> phoneNums(String[] phones) {
        List<String> res = new ArrayList<>();
        Pattern pattern = Pattern.compile("^(139|186)[0-9]{8}$");
        for (String phone : phones) {
            Matcher m = pattern.matcher(phone);
            if (m.find()) {
                res.add(phone);
            }
        }
        return res;
    }

    @Test
    public void test2() {
        String[] ss = { "13988881111" };
        System.out.println(phoneNums(ss));
    }

    @Test
    public void test0() {
        // float a = 0F;
        // int b = 0;
        // System.out.println(a == b);
        int n = 1_000_000;
        int[][][] f = new int[n][n][n];

    }

    // 给定数组nums，从中取出一个子集，使其元素和可以被3整除，求这个子集和的最大值？怎么优化呢？（剪枝）
    List<List<Integer>> res;
    int max, n;
    int[] suf, nums;
    public List<List<Integer>> subByThree(int[] nums) {
        res = new ArrayList<>();
        n = nums.length;
        this.nums = nums;
        suf = new int[n];
        suf[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suf[i] = suf[i + 1] + nums[i];
        }
        dfs(new ArrayList<>(), 0, 0);
        System.out.println(max);
        return res;
    }

    private void dfs(List<Integer> list, int cur, int idx) {
        if (idx == n) {
            if (cur % 3 == 0) {
                if (cur > max) {
                    max = cur;
                    res.clear();
                    res.add(new ArrayList<>(list));
                     System.out.println(max);

                } else if (cur == max) {
                    res.add(new ArrayList<>(list));
                }
            }
            return;
        }
        if (cur + suf[idx] < max) { //剪枝
            return;
        }
        dfs(list, cur, idx + 1); //不添加当前节点
        list.add(nums[idx]);
        dfs(list, cur + nums[idx], idx + 1);//添加当前节点
        list.remove(list.size() - 1);
    }

    @Test
    public void test3() {
        int[] nums = ArrayGenerator.getArray(100, 20);
        System.out.println(subByThree(nums));
    }

    //代码题：给定一些时间区间，判断一个时间点是否在区间里。
    public boolean inTime(int[][] times, int target) {
        Arrays.sort(times, (n1, n2) -> n1[0] == n2[0] ? n1[1] - n2[1] : n1[0]- n2[0]);
        Deque<int[]> deque = new ArrayDeque<>();
        deque.offer(times[0]);
        for (int i = 1; i < times.length; i++) {
            int[] last = deque.peekLast();
            if (last[1] < times[i][0]) {
                deque.offer(times[i]);
            } else {
                if (times[i][1] <= last[1]) {
                    continue;
                } else {
                    deque.pollLast();
                    deque.offer(new int[]{last[0], times[i][1]});
                }
            }
        }

        while (!deque.isEmpty()) {
            int[] cur = deque.pollFirst();
            if (target <= cur[1] && target >= cur[0]) {
                return true;
            }
        }

        return false;
    }

    @Test
    public void test4() {
        int[][] nums = {{0,4}, {3, 7}, {9, 12}};
        System.out.println(inTime(nums, 8));
    }

    //21.int a,b 有几个位是不一样的。（int 几个字节）
    public int diff(int a, int b) {
        int cnt = 0;
        int c = a ^ b;
        while (c != 0) {
            if ((c & 1) == 1) {
                cnt++;
            }
            c >>>= 1;
        }
        return cnt;
    }

    public int addToN(int i, int N) {
        if (i == N) {
            return N;
        }
        return i + addToN(i + 1, N);
    }

    @Test
    public void test5() {
        // System.out.println(diff(2, 6));
        System.out.println(addToN(0, 100));
    }

    //2、手撕代码（10min），给一个数组，找出两个数之和最大，并输出两数的索引？   
    public int[] maxDistance(int[] nums) {
        int a = 0, b = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > a) {
                b = a;
                a = i;
            } else if (nums[i] > b) {
                b = i;
            }
        }
        return new int[]{a,b};
    }

    //从一个字符串中找重复次数最多的子串的重复次数
    public int maxRepeatTime(String s) {
        int max = 1;
        int n = s.length();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n - i; j++) {
                String str = s.substring(j, i + j);
                int t = map.getOrDefault(str, 0) + 1;
                map.put(str, t);
                max = Math.max(t, max);
            }
        }
        return max;
    }

    @Test
    public void test6() {

        // List<Integer> list = new ArrayList<>();
        // list.add(0, 1);
        // System.out.println(list);   
        System.out.println(maxRepeatTime("ccabcabc"));     
    }

}
